In [5]:
%matplotlib inline

import matplotlib
import numpy as np
import matplotlib.pyplot as plt
In [18]:
p = np.linspace(0.001, .99999, 500)
plt.plot(p, -p*np.log2(p))
plt.title('p log p');

(4.1) Verify that the entropy function satisfies the required properties of continuity, non-negativity, monotonicity, and independence.

  • Continuity

p and ln p are both continuous over $0

  • Non-Negativity

Each term of the summation is non-negative. Therefore the full summation is non-negative. $$ 0 \leq p_i \leq 1 \therefore -p_i \log p_i \geq 0$$

  • Monotonicity

I was really confused by this one. I've been told that the question is asking to show that the maximal entropy is monotonic with respect to the number of potential symbols.

The maximum entropy occurs when the symbols are equally probable. For $N$ symbols, this becomes

$$ H = -\sum^N \frac 1 N \log \frac 1 N $$$$ \max H = -\frac 1 N N \log \frac 1 N $$$$ \max H = \log N $$
  • Independence

Is there any more to this than showing that there are no shared terms?

$$H(p,q) = H(p) + H(q) = -\sum p \log p - \sum q \log q $$

Deriving

$$ H(p,q) = -\sum^X \sum^Y p(x,y) \log p(x,y) $$

Since x and y are independent, $ p(x,y) = p(x)p(y)$

$$ H(p,q) = -\sum^X \sum^Y p(x)p(y) \log p(x)p(y) $$$$ H(p,q) = -\sum^X \sum^Y p(x)p(y) \log p(x) - \sum^X \sum^Y p(x)p(y) \log p(y) $$

Rearrange

$$ H(p,q) = -\sum^Y p(y) \sum^X p(x) \log p(x) - \sum^X p(x) \sum^Y p(y) \log p(y) $$

$p(y)$ and $p(x)$ are normalized

$$ H(p,q) = -\sum^X p(x) \log p(x) - \sum^Y p(y) \log p(y) $$

(4.2) Prove the relationships in Equation (4.10). $$I(x,y) = H(x) + H(y) - H(x,y) $$

$$I(x,y) = -\sum_{x}p(x)\log p(x) -\sum_{y}p(y)\log p(y) +\sum_{x}\sum_{y}p(x,y)\log p(x,y) $$$$\sum_x \sum_y p(x,y) \log \frac {p(x,y)}{p(x)p(y)} $$

(4.3) Consider a binary channel that has a small probability $e$ of making a bit error.

(a) What is the probability of an error if a bit is sent independently three times and the value determined by majority voting?

$$ e^3 +3e^2(1-e) $$

In the limit of small $e$, $$3e^2$$

(b) How about if that is done three times, and majority voting is done on the majority voting? $$ 3\big(3e^2\big)^2 $$

(c) If majority voting on majoriy voting on... on majority voting is done N times, how many bits are needed, and what is the probability of an error? How does this probability depend on $e$?

$$ p(i) = 3p(i-1)^2, p(1)=3e^2 $$

Bits: $3^N$

Error: $\propto 3^N e^{2^N}$

Error rate squares every time bits triple.

In [ ]:

(4.4) Calculate the differential entropy of a Gaussian process. $$ H(x) = -\int_\infty^\infty p(x)\log p(x) dx $$

$$ p(x) = \frac {1} {\sqrt {2 \pi \sigma^2} } e^{-x^2/2\sigma^2} $$$$ H(x) = -\int_\infty^\infty p(x)\ln ( \frac {1} {\sqrt {2 \pi \sigma^2} } e^{-x^2/2\sigma^2}) dx $$$$ H(x) = -\int_\infty^\infty \big( \frac {1} {\sqrt {2 \pi \sigma^2} } e^{-x^2/2\sigma^2} \big) \big( \ln \frac {1} {\sqrt {2 \pi \sigma^2} } -\ln \frac {x^2}{2\sigma^2} \big) dx $$$$ H(x) = - \ln \frac {1} {\sqrt {2 \pi \sigma^2} }\int_\infty^\infty \big( \frac {1} {\sqrt {2 \pi \sigma^2} } e^{-x^2/2\sigma^2} \big) \big( -\ln \frac {x^2}{2\sigma^2} \big) dx $$

(4.5) A standard telephone line is specified to have a bandwidth of 3300 Hz and an SNR of 20 dB.

(a) What is the capacity?

$$ f \log \big( 1+\frac S N \big) $$$$ 3300Hz \log \big( 1+10) $$

11,461 bps

(b) What SNR would be necessary for the capacity to be 1 Gbit/s?

1Gb/s / 3,300Hz = 300,000 bits per second

$$ \log_2 (1+S/N) = 3E5 $$$$ 1E^{9} = 3300 \log_2 \big( 1+SNR \big) $$$$ 2^{( 1E^{9} / 3300)} = ( 1+SNR ) $$$$ SNR = 1E6 dB $$

This is nuts